/*
 * @Author: szx
 * @Date: 2022-05-19 14:42:16
 * @LastEditTime: 2022-05-19 18:45:11
 * @Description:
 * @FilePath: \leetcode\面试题\04\12\12.js
 */

var pathSum = function (root, sum) {
    if (root == null) {
        return 0;
    }

    let ret = rootSum(root, sum);
    ret += pathSum(root.left, sum);
    ret += pathSum(root.right, sum);
    return ret;
};

const rootSum = (root, sum) => {
    if (root == null) return 0;

    let ret = 0;
    const val = root.val;
    if (val === sum) ret++;

    ret += rootSum(root.left, sum - val);
    ret += rootSum(root.right, sum - val);
    return ret;
};

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function (root, sum) {
    const map = new Map();
    let res=0;
    const dfs = (root, presum) => {
        if (!root) return 0;
        map.set(presum, (map.get(presum) || 0) + 1);
        let target = presum + root.val;
        res += map.get(target - sum) || 0;
        dfs(root.left, target);
        dfs(root.right, target);
        // 回溯 撤销
        map.set(presum, map.get(presum) - 1);
    };
    return dfs(root, 0);
};
